# Q: Implement a function that prints all possible orderings of the characters
# in a string. In other words, print all permutations that use all the
# characters from the original string. For instance, given the string "hat" your
# function should print the strings "tha", "aht", "tah", "ath", "hta", and
# "hat". Treat each character in the input string as a distinct character, even
# if it is repeated. Given the string "aaa", your function should print "aaa"
# six times. You may print the permutations in any order you choose.
#
# A: All we just need to do is do nested loop, each iterates through the string
# from begining to end. For each index of the loop that collide, we just don't
# do anything. Note that permutation has n! possibility so we need to have 3
# nested loops here. The first one is to pick out which element is to put up
# front. The second one is to pick out which element is to use as the starting
# of the subsequent. The last one is to really generate the elements.
#
# *********** THIS IS NOT CORRECT. NEED TO REWORK COMPLETELY **************

def permutate_string(thestr):
   results = []
   strlen = len(thestr)
   def permutate(pos):
      for i in range(pos, pos+strlen):
         for k in range(i+1, i+strlen):
            buf = [ thestr[i % strlen] ]
            if k % strlen != i:
               for j in range(k, k+strlen):
                  index = j % strlen
                  if index != i:
                     buf.append(thestr[index])
               results.append(''.join(buf))
   for n in range(strlen):
      permutate(n)
   return results


def permutate_string2(thestr):
   results = []
   strlen = len(thestr)
   buf = [None] * strlen
   def permutate(pos):
      if pos == strlen:
         results.apppend(''.join(buf))
         return
      for i in range(pos, pos+(strlen-pos)):
         index = (i % strlen) + base
         buf[pos] = thestr[index]
         permutate(pos+1, (index+1) % strlen)
   permutate(0, 0)
   return results
         

print(permutate_string('tha'))
#print(permutate_string('aaa'))
#print(permutate_string('abcd'))

